package leetcode.d_200_299;

// https://leetcode.cn/problems/count-complete-tree-nodes/
// 完全二叉树的节点个数
public class P222 {
    // 递归法
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    // 利用了完全二叉树的特性
    public int countNodes2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftLevel = getLevel(root.left);
        int rightLevel = getLevel(root.right);
        if (leftLevel == rightLevel) {
            // 左子树肯定是满的
            return (1<<leftLevel) + countNodes(root.right);
        }else{
            // 右子树肯定是满的
            return (1<<rightLevel) + countNodes(root.left);
        }
    }

    public int getLevel(TreeNode root) {
        TreeNode node = root;
        int level = 0;
        while(node != null) {
            level++;
            node = node.left;
        }
        return level;
    }
}
